package 我的Java学习_算法基础.day_03;

import java.util.Arrays;

public class _048_堆排序 {
    public static void main(String[] args) {
        int[] a = {8,5,10,7,4,9,7,2,23};
        heapSort(a);
        System.out.println(Arrays.toString(a));
    }
    static void makeMinHeap(int[] array){
        int n =array.length;
        for(int i = n/2-1;i>=0;i--){
            minHeapFixDown(array,i,n);
        }
    }
    static void minHeapFixDown(int[] array,int i,int length){
        int left = 2*i+1;
        int right = 2*i+2;
        if(left>=length){
            return;
        }
        int min = left;
        if(right>=length){
            min = left;
        }else if(array[right]<array[left]){
            min = right;
        }
        if(array[i]<=array[min]){
            return;
        }
        int temp = array[i];
        array[i] = array[min];
        array[min] = temp;
        minHeapFixDown(array,min,length);

    }
    public static void heapSort(int[] array){
        makeMinHeap(array);
        for(int x =array.length-1;x>=0;x--){
            int temp = array[0];
            array[0] = array[x];
            array[x] = temp;
            minHeapFixDown(array,0,x);
        }
    }

}
